# *-* coding: utf-8 *-*
'''
@author: Geraldo Oliveira
@date: 18 de marco de 2013
@obs: 
Algoritmo de ordenacao HeapSort
'''
import math

class HeapSort(object):
	"""
	Permite ordenar uma lista por ordem
	ascendente recorrendo ao algoritmo
	HeapSort
	"""
	def __init__ (self, lista):
		'''
		Recebe a lista a ordenar

			lista  -> Lista a ordenar
		'''
		self.lista = lista
	
	def swap(self, i, j):
		'''
		Executa a troca de posicoes do metodo HeapSort

		Recebe:
			i 	-> uma das posicoes a trocar
			j 	-> outra posicao de troca
		'''	
		self.lista[i], self.lista[j] = self.lista[j], self.lista[i]

	def heapify(self, end, i):
		'''
		Funcao Heapify do metodo HeapSort
		
		Recebe:
			end -> posicao final
			i 	-> posicao a comparar
		'''
		l=2 * i + 1
		r=2 * (i + 1)
		max=i
		if l < end and self.lista[i] < self.lista[l]:
			max = l
		if r < end and self.lista[max] < self.lista[r]:
			max = r
		if max != i:
			self.swap(i, max)
			self.heapify(end, max)

	def run(self):
		'''	
		Algoritmo HeapSort 
		'''
		end = len(self.lista)
		start = end / 2 - 1
		for i in range(start, -1, -1):
			self.heapify(end, i)
		for i in range(end-1, 0, -1):
			self.swap(i, 0)
			self.heapify(i, 0)

	def nome(self):
		'''
		Devolve o nome do metodo de ordenacao
		'''
		return "heapsort"

	def o(self, n):
		'''
		Calculo do valor teorico

		Recebe:
			n 	-> numero de elementos
		'''
		return (n * math.log(n))

	def __str__(self):
		'''
		Imprime o objecto 
		'''
		return str(self.lista)